import java.util.Arrays;

/**
 * 常见的排序算法
 */
public class Main2 {
    public static void main(String[] args) {
        int[] arr = {4,3,8,1,2,5,13};
        System.out.println(Arrays.toString(arr));

        //quickSort(arr,0,arr.length-1);
        //mergeSort(arr,0,arr.length-1);
        //heapSort(arr,0,arr.length-1);
        //bubbleSort1(arr);
        //insertSort(arr);
        shellSort(arr);
        System.out.println(Arrays.toString(arr));

    }

    // 快速排序 : 递归
    public static void quickSort(int[] arr,int start,int end){

        if(start >= end) return; // 递归出口

        int left = start;
        int right = end;
        int base = arr[left];

        while (left < right){

            while (left < right && arr[right]  > base){
                right--;
            }
            arr[left] = arr[right];

            while (left < right && arr[left]  < base){
                left++;
            }
            arr[right] = arr[left];
        }
        arr[left] = base;  // 基准归位

        quickSort(arr,start,left-1);
        quickSort(arr,left+1,end);
    }


    // 归并排序
    public static void mergeSort(int[] arr,int start,int end){
        if(start >= end) return; // 递归终止条件

        int mid = start + (end-start)/2;   //划分子序列

        mergeSort(arr,start,mid);        //先对左侧子序列进行递归排序
        mergeSort(arr,mid+1,end);  // 再对右侧子序列进行递归排序
        mergeTwoArray(arr,start,mid,end); //合并

    }


    // 合并两个有序数组
    public static void mergeTwoArray(int[] arr,int start,int mid,int end){
        int[] temp = new int[end-start+1];
        int p1 = start;
        int p2 = mid+1;
        int index = 0;

        while(p1 <= mid && p2 <= end){
            if(arr[p1] <= arr[p2]){
                temp[index++] = arr[p1++];
            }else{
                temp[index++] = arr[p2++];
            }
        }

        //如果第一个序列未检测完，直接将后面所有元素加到合并的序列中
        while (p1 <= mid){
            temp[index++] = arr[p1++];
        }

        //如果第二个序列未检测完，直接将后面所有元素加到合并的序列中
        while (p2 <= end){
            temp[index++] = arr[p2++];
        }

        // 复制回原数组
        for(int i = start; i <= end; i++){
            // 注意这里的temp与原数组的关系，可以把temp当初原数组的一个子数组
            arr[i] = temp[i-start];
        }
    }



    // 堆排序  : 先调整大顶堆，交换，递归
    public static void heapSort(int[] arr,int start,int end){

        if(start >= end) return; // 递归出口

        // 1、调整大顶堆
        for (int i = (end-1)/2; i >= 0 ; i--) {
            adjustMaxHeap(arr,i,end);
        }

        // 2、交换 把最大的数和最后一个数交换
        swap(arr,start,end);

        // 3、递归
        heapSort(arr,start,end-1);  //这里的start一定为0
    }

    // 大顶堆 用于升序排序
    // 小顶堆 用于降序排序
    public static void adjustMaxHeap(int[] arr,int index,int lastIndex){
        if(2*index+1 <= lastIndex && arr[index] < arr[2*index+1]){
            swap(arr,index,2*index+1);
        }
        if(2*index+2 <= lastIndex && arr[index] < arr[2*index+2]){
            swap(arr,index,2*index+2);
        }
    }


    // 交换数组位置i和位置j的元素
    public static void swap(int[] arr,int i,int j){
        int temp = arr[i];
        arr[i] = arr[j];
        arr[j] = temp;
    }


    //冒泡排序
    public static void bubbleSort(int[] arr){
        int len = arr.length;
        int temp = 0;
        for (int i = 0; i < len-1; i++) {    // 控制共比较多少轮 len-1轮
            boolean isSorted  = true;
            for (int j = 0; j < len-i-1; j++) {
                if(arr[j] > arr[j+1]){
                    temp = arr[j];
                    arr[j] = arr[j+1];
                    arr[j+1] = temp;
                    isSorted  = false;  // 如果在本轮排序中，元素有交换，则说明数列无序；
                }
            }
            // 如果没有元素交换，说明数列已然有序，直接跳出大循环，就不必再进行后续的比较了
            if(isSorted ){
                break;
            }
        }
    }

    //冒泡排序改进
    public static void bubbleSort1(int[] arr) {
        int tmp;
        int lastExchangeIndex = 0;
        // sortBorder就是无序数列的边界。每一轮排序过程中，
        // sortBorder之后的元素就完全不需要比较了，肯定是有序的。
        int sortBorder = arr.length - 1;
        for (int i = 0; i < arr.length-1; i++) {
            boolean isSorted = true;
            for (int j = 0; j < sortBorder; j++) {
                if (arr[j] > arr[j + 1]) {
                    tmp = arr[j];
                    arr[j] = arr[j + 1];
                    arr[j + 1] = tmp;
                    isSorted = false;
                    lastExchangeIndex = j;
                }
            }
            sortBorder = lastExchangeIndex;
            if (isSorted) {
                break;
            }
        }
    }


    // 插入排序
    public static void insertSort(int[] arr){
        // 默认第一个已经排好序了
        for (int i = 1; i < arr.length; i++) {
            int temp = arr[i];
            int j;
            for (j = i-1; j >= 0 && temp < arr[j] ; j--) {
                arr[j+1] = arr[j];
            }
            arr[j+1] = temp;
        }
    }

    // 希尔排序、带步长的插入排序
    private static void shellSort(int[] arr) {
        int step = arr.length/2; // 初始步长为数组长度的一半
        while(step>=1){
            for (int i = 0; i < step; i++) {
                for (int j = i+step; j < arr.length; j += step) {
                    int temp = arr[j];
                    int k;
                    for (k = j-step; k >= 0 && temp < arr[k]; k -= step) {
                        arr[k+step] = arr[k];
                    }
                    // 注意因为因为for循环时把计算k时减了step，所有这里需要加回来
                    arr[k+step] = temp;
                }
            }
            step = step/2;
        }
    }


}
